package ro;

import java.util.ArrayList;

public class Enumeration {
	ArrayList<Edge> aretes;
	ArrayList<Partition> partitions;
        ArrayList<Partition> sol;
        UFind uf;

        /**
         *
         * @param g The graph parsed from the dot file
         */
	public Enumeration(Graph g){
		//On cree la liste d'aretes grace au graphe
		aretes = g.getArete();
		
		//On dit que toutes les aretes sont inclues
		ArrayList<Boolean > inclusion = new ArrayList<Boolean>();
                sol = new ArrayList<Partition>();
		for(int i = 0 ; i < aretes.size() ; i++){
			inclusion.add(true);
		}
		
		//On cree le UFind
		uf = new UFind(g.getSize());
		
		//Maintenant on cree la liste de partitions, et on y ajoute la partition
		//qui est un ACM avec toutes les aretes a partir de toutes les aretes du graphe
		partitions = new ArrayList<Partition>(); 
		Partition part = kruskal(new Partition(aretes,inclusion));
		
		if(part != null){
			partitions.add(kruskal(new Partition(aretes,inclusion)));
		}
		else{
			System.out.println("Erreur: L'arbre n'est pas connexe");
			System.exit(0);
		}

                partitions.addAll(partitionner(null, partitions.get(0)));
                sol.add(new Partition(partitions.get(0).getAretes(), partitions.get(0).getBool()));
                partitions.remove(0);
                this.calculer_enumeration();
		
	}
	

	/**
         *
         * @param p The partition we want to partition with its mst
         * @param acm the mst of p
         * @return p partitionned with acm
         */
	private ArrayList<Partition> partitionner (Partition p, Partition acm){
		ArrayList<Partition> res = new ArrayList<Partition>();
		ArrayList<Edge> pi=new ArrayList<Edge>(); //La partition pi que l'on va partitionner par son ACM
                ArrayList<Boolean> inclusion= new ArrayList<Boolean>();
                int modifs = 0;

                ArrayList<Edge> Liste_aretes_acm = acm.getAretes();
                if(p==null){ //Si on partitionne le premier ACM p1

                    for(int i=0; i<Liste_aretes_acm.size(); i++){ //On va ajouter les aretes une par une, la premiere fois en 'exclues', puis en 'inclues'
                        for(int j=0; j< i; j++){
                            pi.add(Liste_aretes_acm.get(j));
                            inclusion.add(true);
                        }
                        pi.add(Liste_aretes_acm.get(i));
                        inclusion.add(false);
                        res.add(new Partition(pi, inclusion));
                        pi.clear();
                        inclusion.clear();
                    }
                    return res;
                }
                else{ //Si on partitionne pi avec son acm
                    Liste_aretes_acm.removeAll(p.getAretes());
                    for(int i=0; i<Liste_aretes_acm.size(); i++){
                        for(int k=0; k< p.getAretes().size(); k++){
                            pi.add(p.get(k));
                            inclusion.add(p.getIncl(k));
                        }
                        for(int j = 0 ; j < i ; j++){
                                pi.add(Liste_aretes_acm.get(j));
                                inclusion.add(true);
                        }
                        pi.add(Liste_aretes_acm.get(i));
                        inclusion.add(false);

                        res.add(new Partition(pi, inclusion));
                        pi.clear();
                        inclusion.clear();
                    }
                        
                }
                return res;
	}

        /**
         *
         * @param part The partition from which we want to exctract the MST
         * @return returns the MST or null if there is no MST available for the partition part
         */
	public Partition kruskal(Partition part){
		uf.reset();
		//On cree les listes dont on aura besoin pour renvoyer un
		//ACM sous la forme d'une partition
		ArrayList<Edge> res = new ArrayList<Edge>();
		ArrayList<Boolean> inclusion = new ArrayList<Boolean>();
		
		//list_aretes est la liste des aretes de la partition en entree
		ArrayList<Edge> list_aretes = part.getAretes();
		
		//list_bool est la liste qui indique si les aretes de la partition en entree
		//sont inclues ou pas
		ArrayList<Boolean> list_bool = part.getBool();
		
		//On recupere la liste des peres de uf
		int[] pere = uf.getPeres();
		
		if(part == null){
			return null;
		}
		
		else{
			Edge.triRapide(list_aretes, list_bool);
			for(int i = 0 ; i < list_aretes.size() ; i++){ //Je considere chacune des aretes de ma partition
				if(list_bool.get(i)){ //Si elle sont inclues, je verifie si elles participent a un ACM
					if(uf.union(list_aretes.get(i).source,list_aretes.get(i).target)){
						res.add(list_aretes.get(i));
						inclusion.add(true);
					}
				}
				else{ //Si elles sont exclues, je conserve l'information de leur exclusion
					res.add(list_aretes.get(i));
					inclusion.add(false);
				}
			}
			for(Edge e : aretes ){ 
				if(!res.contains(e)){ //Je parcours toutes les aretes 'ouvertes' / 'libres'
					if(uf.union(e.source,e.target)){ 
						res.add(e);
						inclusion.add(true);
					}
				}
			}
			//La partie suivante ne sert qu'a ne rien renvoyer
			//au cas ou l'arbre n'est pas connexe
			boolean connexe = false;
			for(int i = 0 ; i < pere.length ; i++){
				if ((pere[i] < 0) && connexe){
					return null;
				}
				else if(pere[i] < 0){
					connexe = true;
				}
			}
			
		}
		return new Partition(res,inclusion);
	}


        /**
         * @return Create the list of all graph's ST
         */
        public void calculer_enumeration(){
            int poids_min = 1000000; //Le poids de l'acm courant
            int num_acm = 0; //Le numero de la partition qui donne l'ACM
            int poids_courant=0;
            Partition acm = null;
            int i=0;
            Partition arbre_couvrant=null; //Va stocker les acm calculés de chaque partition
            ArrayList<Partition> temp = null;
            while(!partitions.isEmpty()){
                poids_min=1000000;
                num_acm=-1;
                poids_courant=0;
                acm=null;
                i=0;
                arbre_couvrant=null;
                while( i<partitions.size()){
                    if( (arbre_couvrant=this.kruskal(partitions.get(i))) == null ){
                        partitions.remove(i); //Si l'arbre n'est pas connexe avec la partition p on la supprime

                        i--;
                    }
                    else{
                        if( (poids_courant=arbre_couvrant.getPoids() )<= poids_min){
                            num_acm=i;
                            poids_min=poids_courant;
                            acm=arbre_couvrant;
                        }
                    }
                    i++;
                } //Ici on a recupere la partition qui donne l'ACM
                
                if(num_acm!=-1){

                    sol.add(new Partition(acm.getAretes(), acm.getBool()));
                    temp = partitionner(partitions.get(num_acm), acm);
                    partitions.addAll(temp);
                    partitions.remove(num_acm);
                }
               
            }
        }

        public String toString(){
           if(sol.isEmpty()){
               return "Il n'y a pas de solution";
           }
           else{
               String res = "Voici la liste des arbres couvrants du graphe :\n";

               for(Partition p : sol){
                   res = res + p.toString();
               }

               return res + "\nIl y en a "+sol.size();
            }

    }
}
